This invention relates to control store word-selection systems for controlling the sequence of elementary operations within a central processing unit (CPU). More particularly, the invention relates to branch control means for use in a control store system to increase the flexibility with which control words may be located in a control store.
Many computers built in recent years have utilized control-store control units to control the elementary operations performed by a CPU during the execution of each system instruction. Under control of the control-store control unit, a system instruction is executed by a microprogram which is a sequence of microinstructions (i.e. control words) that control a plurality of elementary operations, some being performed simultaneously and others sequentially. In such systems, the operation code (OP CODE) of the current system instruction is decoded to form the address of the first microinstruction of the microprogram required to perform the system instruction. For example, an eight bit OP CODE provides the ability to perform a 256 way branch to the beginning of up to 256 different microprograms. (A microinstruction is also called a "control word" (CW), and a CW is the coding within a control-word position in the control store.)
Many current computer systems generally have their control stores organized so that a group of control word positions, called a "branch group", are accessed in a single addressing cycle of the control store. Current machine condition state signals determine the selection of one control word position in the addressed branch group in order to obtain the next control word to be executed in the CPU. Basic control store hardware is provided for accessing the control store with a CW select signal which is responsive in part to CW emit signals derived directly from the microinstructions and in part from machine-state signals provided externally to the micro-instructions. The machine-state signal possibilities determine the number of microcode branches available, which often provides fewer CW choices than the number of positions in a branch group. Thus, a choice between two CW's is a two-way branch, etc.
The main advantage of branch group addressing is that it minimizes the time for accessing the next control word by allowing the machine state signal generation and CW selection operations to overlap the accessing of the next branch group of control words in the control store. (The machine-state signal selection of a single control word from available branch choices in an accessed branch group is called a "control store branch operation". Each control word contains a "next address" which is the address of the branch group containing the next control word to be selected.)
In more detail, the next address in the current control word is fed to the control-store address decoder for accessing the next branch group while the outputs of machine-status signal circuits are fed to a branch-address decoder for selecting the CW position containing the microinstruction to be next performed. The required machine-state signals may not be available to a current micro-instruction until after it begins execution. Hence the CPU clock pulses will make the selection in the next CW near the end of a CW clock cycle.
In prior systems, if a given microinstruction is often used in several different micro-routines, the same microinstruction may be stored at several different control word locations within the control store because of different machine-state selection criteria. This replication is one factor which tends to increase the required size of the control store.
A problem that exists in the engineering of CPU controls is that the hardware controls are designed at an earlier time and often by different people than those who design the microprograms which operate the CPU hardware to execute the system instructions architected for the machine. The microprograms which are later designed to control the hardware will inevitably contain branching involving a choice among plural target control words. Such branching must anticipate all of the types of branching possible, e.g. two-way branches, three-way branches, four-way branches, etc. Thus, within a single machine cycle used to execute a single control word, a microprogram branch of up to N ways in an N word branch group may be made. A branch of more than N ways requires more than one control word. It has been found that more than four-way branches are rare. Hence, a branch group having four words can efficiently support almost all microprogram branches in a single machine cycle.
As previously mentioned, the final selection of a control word within a branch group is made near the end of the execution of the current control word cycle in response to the currently existing machine-state signals and the emit field in the current control word. For example, a two-branch in a microprogram may require a choice between the first and fourth control words in a four-word branch group, or perhaps between its first and third words, or between its second and fourth, or between its second and third control words. Likewise, a three-way branch in a microprogram may require a selection among any three words in a four-word branch group, for example, among its first, third and fourth control words, or among its first, second and fourth control words, etc., allowing for all three-way combinations in the branch group. Similarly, a four-way choice must be available among all four control words in a four-word branch group. Furthermore, in some cases only a predetermined one of the control words can be selected.
Thus, any word combination in any branch group might be required by some microprogram branch. Hence, it is desirable that in designing the hardware controls for the control store that total word-selection flexibility be made available to permit any microprogram to make any branch choice among any subset of words in a branch group. Thus, with four control words in a branch group, it is possible to have up to 256 combinatorial branch choices among its four control-word positions, allowing for all Boolean relationships in the selection process.
It is possible to provide a large number of special hardware logic circuits that will support all of these logical Boolean combinations (e.g. 255 circuits) in the selection hardware.
If total selection flexibility is not permitted, it is likely that some control word duplication will result. The consequence is a requirement for a larger control store, which increases costs and may have slower access time. Thus, if control-storage space is limited, for example, by restrictions established in the design specification to meet CPU price and performance criteria, each wasted micro-instruction control-word space can be quite significant. For example, in the design of one prior system in which the specifications called for 2,816 microinstructions, each 90 bits in length and each selected in accordance with the state of two independently varying machine-state control signals (i.e. supporting up to four-way conditional branching), it was found that almost all of the planned control storage matrix space was required to implement the immediately required instructions and their support, so that the amount left in reserve was then insufficient to meet requirements initially specified for reserve. In analyzing the situation more closely, it was found that in excess of one hundred control words were redundant.
A general discussion relating to the method of implementing a microprogram control store can be found in an article entitled "Microprogram Control For System/360" by S. G. Tucker found in the IBM Systems Journal, Vol. 6, No. 4, 1967, pages 222-241. This article is herewith incorporated by reference for its showing of methods of control-store addressing, of microinstruction formats, and of methods for decoding control words and making branch selections.
General prior art is also provided by U.S. Pat. No. 3,391,394 issued July 2, 1968, entitled "Microprogram Control For A Data Processing System" by G. H. Ottaway et al; and U.S. Pat No. 3,800,293 issued Mar. 26, 1974, entitled "Microprogram Control Subsystem" by T. A. Enger et al. Pertinent prior art is found in U.S. Pat. No. 3,325,785 issued June 13, 1967, entitled "Efficient Utilization of Control Storage and Access Controls Therefor", by W. Y. Stevens.
U.S. Pat. Nos. 3,800,293 and 3,391,394 are cited for their general background in the microprogram control area. U.S. Pat. No. 3,325,785 deals with the same problem as the subject invention and finds a different solution to it. U.S. Pat. No. 3,325,785 provides a special hardware translation circuit (branch bit converter) between the machine-state signal generator and the word-selection decoder. Special hardware translation circuits are not used by the subject invention which provides a general solution by means of a bit-pattern register loadable by a special field in the control store data register, and provides a unique word selection decoder circuit for generating the CW selection signal by using the loaded bit pattern to control the translation of the machine-state signals in the generation of the CW selection signals. The bit-pattern register technique of this invention provides an improved practical solution to obtaining CW selection flexibility in an economical manner.